package org.lql.algo.codecrush.hot100.binaryTree;

import org.lql.algo.common.TreeNode;

import java.util.HashMap;

/**
 * @author: liangqinglong
 * @date: 2025-09-07 18:36
 * @description: 437. 路径总和 III <a href="https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class PathSum {

	private HashMap<Long, Integer> prefixSum;
	private int targetSum;

	public int pathSum(TreeNode root, int targetSum) {
		this.targetSum = targetSum;
		// 用于记录前缀和出现的次数
		prefixSum = new HashMap<>();
		// 初始化前缀和为0时的计数为1
		prefixSum.put(0L, 1);
		// 调用dfs函数，计算路径数量
		return dfs(root, 0);
	}

	private int dfs(TreeNode node, long currentSum) {
		if (node == null) {
			return 0;
		}
		// 更新当前路径和
		currentSum += node.val;
		// 计算路径和为targetSum的路径数量
		int pathCount = prefixSum.getOrDefault(currentSum - targetSum, 0);

		// 更新哈希表中当前路径和的计数
		prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) + 1);
		// 递归遍历左子树和右子树
		pathCount += dfs(node.left, currentSum);
		pathCount += dfs(node.right, currentSum);
		// 回溯时，减少当前路径和在哈希表中的计数
		prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) - 1);

		return pathCount;
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(10);
		root.left = new TreeNode(5);
		root.left.left = new TreeNode(3);
		root.left.left.left = new TreeNode(3);
		root.left.left.right = new TreeNode(-2);
		root.left.right = new TreeNode(2);
		root.left.right.right = new TreeNode(1);
		root.right = new TreeNode(-3);
		root.right.right = new TreeNode(11);
		System.out.println(new PathSum().pathSum(root, 8));
	}
}
